using System;
using System.Linq;
using NUnit.Framework;

namespace Solver
{
	/// <summary>
	/// How many circular primes are there below one million?
	/// </summary>
	public class Problem035 : SelfChecker, IProblem
	{
		public int Id
		{
			get { return 35; }
		}

		public string Solve()
		{
			return Solve(1000000).ToString();
		}

		[Test]
		public override void Check()
		{
			Assert.IsTrue(IsComposedOf1379(197));
			Assert.IsFalse(IsComposedOf1379(53));
			Assert.AreEqual(13, Solve(100));
			Assert.AreEqual(55, Solve(1000000));
		}

		private static long Solve(int param)
		{
			var primes = new PrimeNumbersSource("primes-10m.txt")
				.IntPrimes().Skip(4).TakeWhile(p => p <= param).Where(IsComposedOf1379).ToArray();
			var visited = new bool[primes.Length];
			var count = 4;
			for (var i = 0; i < primes.Length; i++)
			{
				if (visited[i]) continue;
				count += CircularCount(i, primes, visited);
			}
			return count;
		}

		private static int CircularCount(int index, int[] primes, bool[] visited)
		{
			var p = primes[index] / 10;
			var length = 1;
			var @base = 1;
			while (p != 0)
			{
				p /= 10;
				length++;
				@base *= 10;
			}
			var cc = 0;
			p = primes[index];
			for (var i = 0; i < length; i++)
			{
				var r = p % 10;
				p = (p / 10) + r * @base;
				var idx = Array.BinarySearch(primes, p);
				if (idx < 0) return 0;
				if (!visited[idx])
				{
					cc++;
					visited[idx] = true;
				}
			}
			return cc;
		}

		private static bool IsComposedOf1379(int p)
		{
			while (p != 0)
			{
				var r = p % 10;
				if (r != 1 && r != 3 && r != 7 && r != 9) return false;
				p /= 10;
			}
			return true;
		}
	}
}